public class InsertionSort {
/*  时间复杂度:
    最坏情况下（数组完全逆序），时间复杂度为 O(n²)。
    最好情况下（数组已经有序），时间复杂度为 O(n)。
    空间复杂度：
    插入排序是原地排序算法，空间复杂度为 O(1)。
    */

    // 插入排序算法实现
    public static void insertionSort1(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前需要插入的元素
            int j = i - 1;

            // 将比 key 大的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入 key 到正确位置
        }
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前的数组:");
        printArray(arr);
        insertionSort1(arr);
        System.out.println("排序后的数组:");
        printArray(arr);
    }
}
